package org.usmile.algorithms.learn.graph.direction;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TopologySortBFS {

    public List<Integer> sort(DirectionAdjSet graph) {
        int[] inDegrees = new int[graph.getV()];
        for (int v = 0; v < graph.getV(); v++) {
            inDegrees[v] = graph.inDegrees(v);
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int v = 0; v < graph.getV(); v++) {
            if (inDegrees[v] == 0) {
                queue.add(v);
            }
        }


        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int v = queue.poll();
            result.add(v);
            for (int w : graph.adj(v)) {
                if (--inDegrees[w] == 0) {
                    queue.add(w);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        DirectionAdjSet graph = new DirectionAdjSet(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
//        graph.addEdge(3, 0);
        graph.addEdge(3, 2);
        graph.addEdge(2, 4);
        graph.addEdge(4, 3);

        System.out.println(new TopologySortBFS().sort(graph));
    }
}
